import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.IntStream;

/**
 * 请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。
 * <p>
 * 请你实现 SeatManager 类：
 * <p>
 * SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
 * int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
 * void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。
 */

public class SeatManager {
//    int[] arr;
//    int minIndex = 1;
//    public SeatManager(int n) {
//        arr = new int[n];
//    }
//
//    public int reserve() {
//        //1 表示已占用
//        int temp = minIndex;
//        arr[minIndex-1] = 1;
//        boolean has = false;
//        for (int i = minIndex ; i < arr.length  ; i++) {
//            if(arr[i] == 0){
//                has = true;
//                minIndex = i+1;
//                break;
//            }
//        }
//        if(!has){
//            minIndex =arr.length;
//        }
//        return temp;
//    }
//
//    public void unreserve(int seatNumber) {
//        if(seatNumber <= minIndex ){
//            minIndex = seatNumber;
//        }
//        arr[seatNumber-1] = 0;
//    }
    public static void main(String[] args) {
        SeatManager seatManager = new SeatManager(2); // 初始化 SeatManager ，有 5 个座位。
        seatManager.reserve();
        seatManager.unreserve(1);// 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
        seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
        seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
        seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
        seatManager.reserve();
        seatManager.unreserve(1);/// 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
        seatManager.reserve();
        seatManager.unreserve(2);/// 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
        seatManager.reserve();    // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
    }

    //以set方式实现
//    Set<Integer> set = new TreeSet<>();
//    public SeatManager(int n) {
//        for (int i = 1; i < n; i++) {
//            set.add(i);
//        }
//    }
//
//    public int reserve() {
//        //1 表示已占用
//        Integer res = set.iterator().next();
//        set.remove(res);
//        return res;
//    }
//
//    public void unreserve(int seatNumber) {
//        set.add(seatNumber);
//    }
    //以队列的形式实现
    PriorityQueue<Integer> queue;
    public SeatManager(int n) {
        queue = new PriorityQueue<>(IntStream.rangeClosed(1,n).boxed().toList());
    }

    public Integer reserve() {
        return queue.poll();

    }

    public void unreserve(int seatNumber) {

        queue.offer(seatNumber);
    }
}


